#include "../../tools.h"
using std::max_element;

class Solution {
public:
    int jump(vector<int>& nums) {
        vector<int> dp(nums.size(), 100);
        dp[nums.size() - 1] = 0;

        for(int i = nums.size() - 2; i > -1; --i){
            int bound = i + nums[i] > nums.size() - 1? nums.size() - 1: i + nums[i];
            dp[i] = *min_element(dp.begin() + i, dp.begin() + bound + 1) + 1;
            cout <<i << " " << bound << " " << dp[i] << endl;
        }
        return dp[0];
    }
};

int main(int argc, char const *argv[])          
{
    vector<int> nums = {2,3,1,1,4};
    
    Solution s;
    cout << s.jump(nums);

    return 0;
}
